class Solution {
public:
    int reversePairs(vector<int>& re) {
        vector<int> tmp(re.size());
        return mysort(re,0,re.size()-1,tmp);
    }

    int mysort(vector<int>& re,int left,int right,vector<int>& tmp)
    {
        if(left>=right) return 0;
        int mid=left+(right-left)/2;
        int ret=0;
        //[left,mid] [mid+1,right]
        ret+=mysort(re,left,mid,tmp);
        ret+=mysort(re,mid+1,right,tmp);
        int cur1=left;
        int cur2=mid+1;
        int i=0;
        while(cur1<=mid&&cur2<=right)
        {
            if(re[cur1]<=re[cur2])
            {
                tmp[i++]=re[cur1++];
            }
            else if(re[cur1]>re[cur2])
            {
                tmp[i++]=re[cur2++];
                ret+=mid-cur1+1;
            }
        }
        while(cur1<=mid) tmp[i++]=re[cur1++];
        while(cur2<=right) tmp[i++]=re[cur2++];         
        for(int k=0;k<i;++k)
        {
            re[left+k]=tmp[k];
        }
        return ret;
    }
};
